#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


 // Definition for singly-linked list.
  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL){
            return NULL;
        }
        ListNode* low = head;
        ListNode* fast = head;
        
        while(true){
            if(low->next==NULL){
                return NULL;
            }
            if(fast==NULL){
                return NULL;
            }
            
            low = low->next;
            if(fast->next == NULL){
                return NULL;
            }
            fast = fast->next->next;
            if(low == fast){
                break;
            }
        }
        fast = head;
        while(fast!=low){
            fast = fast->next;
            low = low->next;
        }
        return low;
    }
};

int main(){
    Solution S;
    ListNode* head = new ListNode(3);
    head->next = new ListNode(2);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(-4);
     head->next->next->next->next =  head->next;
    ListNode* newNode = S.detectCycle(head);
    return 0;
}

